#ifndef DATA_STRUCTURE_AMGRAPH_H
#define DATA_STRUCTURE_AMGRAPH_H

#include "ALGraph.h"
#include<cmath>

class AMGraph : public Graph {
private:
    verType vexs[MVNum];
    ArcType matrix[MVNum][MVNum] = {MaxInt};//邻接矩阵
protected:
    verType findNode(int i) override {
        return vexs[i];
    }

    void DFSS(int v1, int v2, bool visited[], string outStr, bool *ok) {
        outStr += vexs[v1];
        if (v1 == v2) {
            cout << outStr;
            *ok = true;
        }
        outStr += "->";
        visited[v1] = true;
        for (int vi = 0; vi < MVNum; ++vi) {
            if (matrix[v1][vi] < MaxInt && !visited[vi]) {
                DFSS(vi, v2, visited, outStr, ok);
            }
        }
    }

public:
    AMGraph(int vexNum, int arcNum) : Graph(vexNum, arcNum) {
        for (int i = 0; i < MVNum; ++i) {//初始化
            for (int j = 0; j < MVNum; ++j) {
                matrix[i][j] = MaxInt;
            }
        }
        this->create();
    }

    void inputNode(int idx) {
        cin >> vexs[idx];//输入点信息
    }

    void inputArc() {
        verType v1, v2;
        ArcType w;
        cin >> v1 >> v2 >> w;
        int i = findVexIdx(v1);
        int j = findVexIdx(v2);
        matrix[i][j] = w;
    }

    void DFS(verType v1, verType v2) override {
        bool visited[vexNum];
        memset(visited, false, sizeof(visited));
        bool ok = false;
        DFSS(findVexIdx(v1), findVexIdx(v2), visited, "", &ok);
        if (!ok) {
            cout << "该两点没有联通路径" << endl;
        }
    }

    void BFS(verType v1, verType v2) override {
        bool visited[vexNum];
        memset(visited, false, sizeof(visited));
        queue<ListNode *> *queue = new std::queue<ListNode *>;
        int idx = findVexIdx(v1);
        int end = findVexIdx(v2);
        bool ok = false;

        queue->push(new ListNode(idx));
        visited[idx] = true;
        while (!queue->empty()) {
            ListNode *vi = queue->front();
            if (vi->idx == end) {
                cout << vexs[vi->idx];
                vi = vi->next;
                for (; vi != nullptr; vi = vi->next) {
                    cout << "<-" << vexs[vi->idx];
                }
                cout << endl;
                ok = true;
                break;
            }
            queue->pop();
            for (int w = 0; w < MVNum; w++) {
                if (matrix[vi->idx][w] < MaxInt && !visited[w]) {
                    queue->push(new ListNode(w, vi));
                    visited[w] = true;
                }
            }
        }
        if (!ok) {
            cout << "该两点没有联通路径" << endl;
        }
    }
};


Graph *createGraphTool() {
    int vexNum, arcNum;
    cout << "输入点数和边数:";
    cin >> vexNum >> arcNum;
    if (arcNum < vexNum * log(vexNum) / log(2)) {
        cout << "根据数据类型鉴定为稀疏图，创建邻接表图" << endl;
        return new ALGraph(vexNum, arcNum);
    } else {
        cout << "根据数据类型鉴定为稠密图，创建邻接矩阵图" << endl;
        return new AMGraph(vexNum, arcNum);
    }
}

#endif //DATA_STRUCTURE_AMGRAPH_H
